package leetcode.code1423;

import leetcode.IDebug;

//超出内存限制 26 / 40 个通过测试用例
public class Solution2 implements IDebug {

	public int maxScore(int[] cardPoints, int k) {
		int len = cardPoints.length;
		Integer[][][] dp = new Integer[len][len][k + 1];
		return this.find(cardPoints, 0, len - 1, k, dp);
	}

	private int find(int[] cardPoints, int left, int right, int k, Integer[][][] dp) {
		if (k == 1 || (k > 0 && left == right)) {
			int max = Math.max(cardPoints[left], cardPoints[right]);
			dp[left][right][k] = max;
			return max;
		}
		if (dp[left][right][k] != null) {
			return dp[left][right][k];
		}
		int max = cardPoints[left] + this.find(cardPoints, left + 1, right, k - 1, dp);
		max = Math.max(max, cardPoints[right] + this.find(cardPoints, left, right - 1, k - 1, dp));
		dp[left][right][k] = max;
		return max;
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
